#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAXN = 40600;
const LL maxNum = MAXN*MAXN;
int prime[MAXN], p_cnt;
LL mu[MAXN];
LL muSum[MAXN];
bool not_p[MAXN];
void Init() {
    p_cnt=0;
    mu[1] = 1;
    for (int i=2; i<MAXN; ++i) {
        if (!not_p[i]) {
            prime[p_cnt++] = i;
            mu[i] = -1;
        }
        for (int j=0; j<p_cnt&&prime[j]*i<MAXN; ++j) {
            not_p[i*prime[j]] = true;
            if (i%prime[j]==0) {
                mu[i*prime[j]] = 0;
                break;
            }
            mu[i*prime[j]] = -mu[i];
        }
    }
    muSum[0] = 0;
    for (int i=1; i<MAXN; ++i) muSum[i] = muSum[i-1] + mu[i];
}
LL solve(LL ask) {
    LL ret = 0;
    for (LL i=1, last; i*i<=ask; i=last+1) {
        last = sqrt(ask/(ask/(i*i)));
        ret += (muSum[last] - muSum[i-1])*(ask/(i*i));
    }
    return ret;
}

int main() {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    Init();
    int T;
    cin>>T;
    LL ask;
    while (T--) {
        scanf("%lld", &ask);
        LL l=0, r=maxNum;
        while (l+1<r) {
            LL mid = (l+r) / 2;
            LL ret = solve(mid);
            if (ret>=ask) r = mid;
            else l = mid;
        }
        printf("%lld\n", r);
    }
    return 0;
}
